1. Field of the Invention
The present invention is related to a method and system to be utilized in data communications. In particular, the present invention is related to a method and system to be utilized in data communications involving at least one data communications network.
2. Description of the Related Art
Data communications is the transfer of data from one or more sources to one or more sinks that is accomplished (a) via one or more data links between the one more sources and the one or more sinks (b) according to a protocol. A data link is the means of connecting communications facilities or equipment at one location to communications facilities or equipment at another location for the purpose of transmitting and receiving data. A protocol, in communications, computer, data processing, and control systems, is a set of formal conventions that govern the format and control the interactions between at least two communicating functional elements in order to achieve efficient and understandable communications. Examples of protocols are Internet Protocol (IP) and Asynchronous Transfer Mode (ATM) protocol.
A data communications network is the interconnection of three or more communicating entities (i.e., data sources and/or sinks) over one or more data links. A data communications network connects and allows communication between multiple data sources and multiple data sinks over one or more data links. The concept of a data link includes the media connecting the one or more data sources to one or more data sinks, as well as the data communications equipment utilizing the media. The data communications networks utilize protocols to control the interactions between data sources and sinks communicating over the one or more data links. Thus, it follows that such protocols must take into account the data communications requirements of data sources and sinks desiring communication over the one or more data links.
Referring now to FIG. 1, shown is a partially-schematic diagram of a related art data communications network. Depicted are six data sources/sinks: data source/sink A 100, data source/sink B 102, data source/sink C 104, data source/sink D 106, data source/sink E 108, and data source/sink F 110. The depicted six data sources/sinks are connected by/through data communications network 112. Illustrated is that data communications network 112 is composed of numerous data communications links 150-184 and network nodes 116-128. Shown is that within each network node 116-128 resides crossbar switches 130-142, respectively.
Historically, each crossbar switch 130-142, was a switch that had a number of vertical paths, a number of horizontal paths, and electromagnetic-operated mechanical devices, i.e., electromechanical relays, for interconnecting any one of the vertical paths with any one of the horizontal paths. (While the foregoing is historically truth those skilled in the art will recognize that the logical functions of crossbar switches are generally performed using combinational circuits; however, the term xe2x80x9ccrossbarxe2x80x9d switch has been retained for such combinational circuits even though such circuits typically no longer actually utilize a true physical xe2x80x9ccrossbar.xe2x80x9d) Thus, the electromagnetic-operated mechanical devices within each crossbar switch 130-142 can be utilized to interconnect at least one data communications link on one side of any particular crossbar switch to at least one data communications link on the other side of the particular crossbar switch. For example, crossbar switch 130 internal to network node 116 contains circuitry sufficient to connect any one of data communications links 150-154 with any one of data communications links 156-162. Likewise, crossbar switch 136 internal to network node 122 contains circuitry sufficient to connect any one of data communications link 163, 166, 170 with any one of data communications links 174-176. The same holds true for the other crossbar switches depicted in FIG. 1.
When data communications is desired between any two data sources/sinks (e.g., data source/sink A 100 with data source/sink D 106, data source/sink B 102 with data source/sink F 100, or data source/sink C 104 with data source/sink E 108) appropriate crossbar switches 130-142 can be utilized to establish hardwire paths between the data source/sink pair. At present, there are two basic ways in which crossbar switches 130-142 can be utilized to establish a communications path through data communications network 112: (1) by use of what is known in the art as xe2x80x9ccircuit switchingxe2x80x9d; and (2) by use of what is known in the art as xe2x80x9cpacket switching.xe2x80x9d The present invention is related to crossbar switches in packet-switched networks. However, before packet-switched networks are discussed, the functioning of crossbar switches in a circuit-switched network is discussed because discussing the functioning of crossbar switches in a circuit switched network serves as a good introduction to discussing the functioning of crossbar switches in packet-switched networks.
Referring now to FIG. 2, shown are three xe2x80x9ccircuit switchedxe2x80x9d paths which are used to introduce the functioning of crossbar switches. In what is known in the art as xe2x80x9ccircuit switching,xe2x80x9d an actual physical circuit is established between each data source/sink pair. Depicted in FIG. 2 is circuit switched path 1 connecting data source/sink A 100 with data source/sink D 106. Illustrated is that circuit switched path 1 is composed of data communications link 150-network node 116-data communications link 162-network node 126-data communications link 178-network node 124-data communications link 170-network node 122-data communications link 174. With respect to circuit switched path 1, shown is that crossbar switch 130 connects data communications link 150 with data communications link 162, crossbar switch 140 connects data communications link 162 with data communications link 178, crossbar switch 138 connects data communications link 178 with data communications link 170, crossbar switch 136 connects data communications link 170 with data communications link 174. Also depicted is circuit switched path 2 connecting data source/sink B 102 with data source/sink F 110. Circuit switched path 2, and each of the depicted components making up circuit switched path 2, functions in a manner similar to that described in relation circuit switched path 1. Further depicted is circuit switched path 3 connecting data source/sink C 104 with data source/sink E 108. Circuit switched path 3, and each of the depicted components making up circuit switched path 3, also functions in a manner similar to that described in relation circuit switched path 1.
Referring now to FIG. 3, shown is the use of xe2x80x9cpacket switchingxe2x80x9d to transmit data through data network 112, and how crossbar switches are utilized in a packet-switched network. In what is known in the art as xe2x80x9cpacket switching,xe2x80x9d data to be transmitted between each data source/sink pair is encapsulated in a xe2x80x9cpacketxe2x80x9d which, in data communications, is a sequence of binary digits that (a) includes data, control signals, and possibly error control signals, and (b) is arranged in a specific format, such as a header part and data part, wherein the header part generally contains information indicative of the source and destination of the data part of the packet (thus, as used, the term xe2x80x9cpacketxe2x80x9d includes all such unitized data, such as, for example IP packets or ATM cells. Whereas in circuit switching, crossbar switches 130-142 were keyed to and switched, or controlled, upon the basis of a circuit to be established throughout data communications network 112 throughout the duration of a call, in xe2x80x9cpacket switchingxe2x80x9d crossbar switches 130-142 are keyed to, and switched upon, the basis of header information (e.g., the source and destination information contained within the header). That is, each crossbar switch 130-142 typically has some intelligence sufficient to (1) xe2x80x9creadxe2x80x9d the source and destination information of a packet received into the crossbar switch from a data communications link serving as input to the crossbar switch, (2) on the basis of such read source and destination information determine the appropriate data communications link to serve as output from the crossbar switch, (3) establish a connection between the input data communications link and output data communications link, and (4) thereafter transmit the packet across a switch.
Depicted in FIG. 3 are packets 300-316. Illustrated is that packets 300-304 contain data originating at data source/sink A 100 and destined for data source/sink data source/sink D 106, a fact reflected in the headers of packets 300-304. In addition, shown is that the headers of packets 300-304 are also numbered relative to each other, so that the packets can be placed in their appropriate order upon receipt at data source/sink D 106. Illustrated is that packets 306-310 contain data originating at data source/sink B 102 and destined for data source/sink data source/sink E 108, a fact reflected in the headers of packets 306-310. In addition, shown is that the headers of packets 306-310 are also numbered relative to each other, so that the packets can be placed in their appropriate order upon receipt at data source/sink E 108. Illustrated is that packets 312-314 contain some data originating at data source/sink C 104 and destined for data source/sink D 106, some data originating at data source/sink C 104 and destined for data source/sink E 108, some data originating at data source/sink C 104 and destined for data source/sink F 110, a fact reflected in the headers of packets 312-316.
Inspection of data communications network 112 shows that there are multiple paths through data communications network 112 from any data source/sink A 100, data source/sink B 102, or data source/sink C 104, to any data source/sink D 106, data source/sink E 108, or data source/sink F 110. Since packet switching is being utilized, each crossbar switch 130-142 is rapidly switching between various inputs and outputs in response to the source and destination information in each packet received on each input of each such crossbar switch 130-142. This rapid switching is illustrated by the dashed lines connecting the data communications links on either side of the crossbar switches 130-142.
Those skilled in the art will recognize that there are two basic ways in which packets are transmitted through a packet switched network: the datagram method and the virtual circuit method. In the datagram method, each packet is treated independently. That is, each network node 116-128 makes an independent routing decision for each packet received, irrespective of similarly addressed packets previously received. Consequently, it is likely that packets, even if they have the same destination address, will not all follow the same route through data communications network 112, and thus it will be up to the destination data source/sink to reassemble the packets in the correct order upon receipt. In the virtual circuit approach, a fixed route from a particular data source/sink to a particular data source/sink, through designated network nodes of data communications network 112, is established prior to any packets are sent. Thereafter, all packets from the particular data source/sink to the particular data source/sink will follow the fixed route through data communications network 112 thereby ensuring that any packets so transmitted arrive at the destination data source/sink in the order in which such packets were transmitted.
In the early days of data communications networks, circuit switching was used for data communications requiring near continuous transmission and reception (e.g. full motion video and/or continuous audio), while packet switching which used for virtually all other types of data. However, in more recent times a move has been made in the industry to utilize packet switching, even for data communications traditionally thought to require near continuous transmission and reception. Examples of this are seemingly continuous voice and data over Internet Protocol (IP) or Asynchronous Transfer Mode (ATM) networks. This is achieved by a digitizing, segmenting, packetizing, transmitting, unpacketizing, re-assembling, and displaying the data at a speed sufficient such that human perception cannot detect discontinuity in the data.
As packets transit data communications network 112, it is possible and indeed likely that multiple packets will converge upon a particular network node substantially simultaneously and/or in rapid succession. An illustration of such an event is depicted in FIG. 4, wherein is shown network node 122 containing crossbar switch 136. Depicted is that nine packets which were illustrated in FIG. 3 as being generated by data sources/sinks A 100, B 102, and C 104 are converging upon network node 122. Notice that two of the first packets that will be received by network node 122, at what will be assumed to be substantially the same time, are both directed to data source/sink 106 (e.g., packet 304 and 312) which resides on data communications link 174. Packet 304 arrives at network node 122 via data communications link 166 while packet 312 arrives at network node 122 via data communications link 170 at substantially same time.
As those skilled in the art will appreciate, by its nature crossbar switch 136 can only connect one data communications link to data communications link 174 at any particular instant in time. Thus, one or the other of data packets 304 and 312 will have to wait, typically in a buffer, depending upon which of data packets 304 and 312 crossbar switch 136 decides to transmit first.
In the early days of packet switched networks, the fact that data packets might have to wait for transmission at a particular network node did not pose that great of a problem, and such delays were in the main tolerated. However, the use of packet switching for such data communications requiring near continuous transmission and reception has given rise to a need to be able to schedule which packets will have to wait, and which will be directly transmitted through a particular node by a particular crossbar switch, since it is critical that such traffic (network traffic consisting of data requiring near continuous transmission reception, such as full motion video and/or audio) experience substantially minimal delays at network nodes as such traffic transits data communications network 112.
The need for scheduling packets through a particular crossbar switch that is resident within a particular network node has been met by the creation of what are known in the art as xe2x80x9cschedulersxe2x80x9d. These schedulers use a variety of different schemes to ensure that data packets designated as having xe2x80x9chighxe2x80x9d or xe2x80x9chigherxe2x80x9d priority, relative to other data packets waiting for transmission through a particular crossbar switch, are transmitted prior to data packets having relatively xe2x80x9clowxe2x80x9d or xe2x80x9clowerxe2x80x9d priority.
Schedulers in existence do a passable job of ensuring that the relatively xe2x80x9chighxe2x80x9d or xe2x80x9chigherxe2x80x9d data packets transit particular crossbar switches relatively efficiently. However, recall from the discussion above that other traffic exists on data communications network 112 which, although of a xe2x80x9clowxe2x80x9d or xe2x80x9clowerxe2x80x9d priority, still needs to transit data communications network 112. Unfortunately, virtually all schedulers in existence focus on assuring that the relatively xe2x80x9chighxe2x80x9d or xe2x80x9chigherxe2x80x9d priority data packets transit particular crossbar switches in an efficient manner, and then rely on network xe2x80x9cslack,xe2x80x9d or a momentary decrease in data traffic loading at the particular crossbar switches to allow the transmission of the relatively a xe2x80x9clowxe2x80x9d or xe2x80x9clowerxe2x80x9d priority data packets through the particular crossbar switches.
The foregoing referenced scheduler schemes initially worked relatively well. However, increasing data communications network traffic has made it more and more likely that insufficient slack will manifest itself within the network sufficient to allow the transmission of the low or lower priority data packets through the particular crossbar switches. The result of this is typically buffer (temporary packet storage available within circuitry substantially proximate to the associated particular crossbar switch, such circuitry being known in the art as the crossbar xe2x80x9cswitch fabricxe2x80x9d) overloading and subsequent loss of data at the particular crossbar switches. The inability to transmit such low or lower priority data packets through one or more particular crossbar switches is known in the art as xe2x80x9cstarvingxe2x80x9d the low or lower priority data packets by denying them network bandwidth necessary for them to remain in existence.
Those skilled in the art will recognize that although certain data packets have been designated to be of a relatively low or lower priority in a data network communications sense, such data is still important to the persons from whom and to whom it is directed. Accordingly, it is apparent that a need exists in the art for a method and system which will substantially alleviate the starving of relatively low or lower priority data packets while substantially insuring that relatively high or higher priority data packets transit a particular crossbar switch with relatively low delay.
It has been discovered that a method and system can be achieved which will substantially alleviate the starving of relatively low or lower priority data packets at a particular crossbar switch within a data communications network while substantially ensuring that relatively high or higher priority data packets transit that same particular crossbar switch with relatively low delay. The method and system substantially ensure that actual data transmission per unit time from at least one cross-point buffer switch ingress to at least one cross-point buffer switch egress substantially satisfies a designated target amount of actual data transmission per unit time.
The foregoing is a summary and thus contains, by necessity, simplifications, generalizations and omissions of detail; consequently, those skilled in the art will appreciate that the summary is illustrative only and is not intended to be in any way limiting. Other aspects, inventive features, and advantages of the present invention, as defined solely by the claims, will become apparent in the non-limiting detailed description set forth below.